package com.kevin.learn.leetcode;

import com.alibaba.fastjson.JSON;
import com.kevin.learn.domain.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 652
 */
public class 寻找重复子树 {

    // 记录所有子树
    public static HashMap<String, Integer> memo = new HashMap<>();
    // 记录重复的子树根节点
    public static LinkedList<TreeNode> res = new LinkedList<>();


    public static void main(String[] args) {
        TreeNode treeNode = initData();
        List<TreeNode> duplicateSubtrees = findDuplicateSubtrees(treeNode);
        System.out.println(JSON.toJSON(duplicateSubtrees));
    }

    /* 主函数 */
    public static List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    /* 辅助函数 */
    public static String traverse(TreeNode root) {
        if (root == null) {
            return "#";
        }

        String left = traverse(root.left);
        String right = traverse(root.right);

        String subTree = left + "," + right + "," + root.data;

        int freq = memo.getOrDefault(subTree, 0);
        // 多次重复也只会被加入结果集一次
        if (freq == 1) {
            res.add(root);
        }
        // 给子树对应的出现次数加一
        memo.put(subTree, freq + 1);
        return subTree;
    }

    private static TreeNode initData() {
        TreeNode treeNode = new TreeNode(1);

        // 左
        TreeNode left2 = new TreeNode(2);
        TreeNode left4 = new TreeNode(4);


        left2.setLeft(left4);
        treeNode.setLeft(left2);

        // 右
        TreeNode right3 = new TreeNode(3);

        treeNode.setRight(right3);

        return treeNode;
    }
}
